#include <stdlib.h>
#include <stdio.h>
#include <string.h>


#include "graph.h"
#include "erros.h"
#include "lista_ligada.h"
#include "queue.h"




struct node{					//definiçao de um nó generico
	unsigned int index;			//numero do vertice ou aresta
	Node prev;					//apontador para o nó anterior
	Node next;					//apontador para o nó seguinte
	Node adj;					//apontador para a lista de adjências
	void *Elem;					//apontador para o elem da lista
	unsigned int Visit;			//marcação de vértice visitado. Se zero, não foi visitado
};


typedef struct vertex *Vert;

struct vertex{					//definiçao de um vertice
	unsigned int inDegr;		//grau incidente
	unsigned int outDegr;		//grau emergente
	void *Info;					//informaçao contida no vertice

/*	char *Nome;					//Nome do utilizador
	char *Nickname;				//Nickanem do utilizador
	char *Mail;					//Mail do utilizador
	char *Morada;				//Morada do utilizador
	unsigned int pontos;		//Pontos que o utilizador já tem por ter visistado lugares
 */
};


typedef struct edge *Edge;

struct edge{					//definiçao de uma aresta
	int cost;					//custo associado a aresta
};


struct graph{					//definiçao do grafo
	Node head;					//apontador para cabeça do grafo
	unsigned int numVert;		//numero de vertices do grafo
	unsigned int numEdge;		//numero de arestas do grafo
};

//-------------
static Vert createVert();
static Edge createEdge(int);
static Node createNode(unsigned int);
static void destroyNode(Node*);
static Node inPosition(Node, unsigned int);
static Node outPosition(Node, unsigned int);
//--------------


Graph createGrap(){
	Graph grafo;
	if ((grafo = (Graph)malloc(sizeof(struct graph))) == NULL)
		return NULL;

	grafo->head = NULL;			//inicializa cabeça do grafo
	grafo->numVert = 0;
	grafo->numEdge = 0;
	return grafo;
}


int destroyGraph(Graph *ptr){
	Graph aux = *ptr;
	Node vert, edge;

	if(aux==NULL) return NO_GRAPH;

	while(aux->head != NULL){				//liberta memoria ocupada pelos vertices do grafo
		vert=aux->head;
		aux->head = aux->head->next;		//actualiza cabeça

		while(vert->adj != NULL){			//liberta memoria ocupada pelas arestas do vertice
			edge = vert->adj;				//cabeça da lista das arestas
			vert->adj = vert->adj->next;
			free(edge->Elem);				//liberta memoria da aresta
			free(edge);						//iberta nó da lista de arestas
		}
		free(vert->Elem);					//liberta memoria do vertice
		free(vert);							//liberta no da lista de vertices
	}
	free(aux);								//liberta memoria ocupada pelo grafo
	*ptr = NULL;							//referencia do grafo a NULL
	return OK;
}


Graph copyGraph(Graph ptr){
	if(ptr == NULL) return NULL;
	Graph grafo;
	if ((grafo = (Graph)malloc(sizeof(struct graph))) == NULL)
		return NULL;

	grafo->head = ptr->head;
	grafo->numVert = ptr->numVert;
	grafo->numEdge = ptr->numEdge;
	return grafo;

}


int insertVert(Graph ptr, unsigned int vert){
	Node nodeIns, newVert;
	if(ptr == NULL) return NO_GRAPH;

	if((newVert = createNode(vert)) == NULL) return NO_MEM;		//criar nó
	if((newVert->Elem = createVert()) == NULL){					//criar vertice
		free(newVert);
		return NO_MEM;}

	if(ptr->head == NULL || ptr->head->index > vert){			//inserir a cabeça do grafo
		newVert->next = ptr->head;
		ptr->head = newVert;
		if(newVert->next != NULL) newVert->next->prev = newVert;
	}

	else{														//inserir a frente do no de inserçao
		if((nodeIns = inPosition(ptr->head, vert)) == NULL){
			destroyNode(&newVert);								//vertice ja existe
			return VERT_REP; }
		newVert->next = nodeIns->next;
		if(newVert->next != NULL) newVert->next->prev = newVert;
		newVert->prev = nodeIns;
		nodeIns->next = newVert;
	}
	ptr->numVert++;												//actualiza num de vertices
	return OK;
}


int removeVert(Graph ptr, unsigned int vert){
	Node rem;													//posiçao de remoçao do vertice
	Node vert2, edg;
	Vert vertice;

	if(ptr == NULL) return NO_GRAPH;
	if(ptr->numVert == 0) return GRAPH_EMPTY;

	if((rem = outPosition(ptr->head, vert)) == NULL) return NO_VERT;	//determinar posiçao de remoçao do vertice

	while(rem->adj != NULL){									//remover lista adjacencias do vertice
		edg = rem->adj;											//cabeça da lista de arestas
		vertice = (Vert)edg->adj->Elem;
		vertice->inDegr--;										//actualizar grau incidente
		rem->adj = rem->adj->next;								//actualizar cabeça
		destroyNode(&edg);										//destruir no com a aresta
		ptr->numEdge--;											//actualizar numero de arestas
	}
	if(rem == ptr->head){
		if(rem->next != NULL) rem->next->prev = NULL;			//remoçao do vertice na cabeça do grafo
		ptr->head = rem->next;}
	else{
		rem->prev->next = rem->next;							//remoçao de outro vertice do grafo
		if(rem->next != NULL) rem->next->prev = rem->prev;
	}
	destroyNode(&rem);											//destruir no com vertice
	ptr->numVert--;												//actualizar numero de vertices

	vert2 = ptr->head;
	while(vert2 != NULL){										//remover arestas incidentes
		if((edg = outPosition(vert2->adj, vert)) != NULL){		//remover aresta deste vertice para o vertice removido
			if(edg == vert2->adj){
				if(edg->next != NULL) edg->next->prev = NULL;	//remover a aresta da cabeça da lista de arestas
				vert2->adj = vert2->adj->next;}
			else{												//remoçao de outra aresta da lista de arestas
				edg->prev->next = edg->next;
				if(edg->next != NULL)
					edg->next->prev = edg->prev;}

			vertice = (Vert)vert2->Elem;
			vertice->outDegr--;									//actualizar grau emergente
			destroyNode(&edg);									//destruir no com aresta
			ptr->numEdge--;										//actualizar numero de arestas
		}
		vert2 = vert2->next;									//vertice seguinte do grafo
	}
	return OK;
}


int insertEdge(Graph ptr, unsigned int vert1, unsigned int vert2, int pcost){
	Node nodeIns, nodeAux;										//posiçao de inserçao e nova aresta
	Node pvert1, pvert2;										//posiçao dos vertices adjacentes
	Vert vertice;

	if(ptr == NULL) return NO_GRAPH;
	if(ptr->numVert == 0) return NO_VERT;
	if(vert1 == vert2) return EDGE_REP;
																//verificar se os vertices existem
	if((pvert1 = outPosition(ptr->head, vert1)) == NULL)
		return NO_VERT;
	if((pvert2 = outPosition(ptr->head, vert2)) == NULL)
		return NO_VERT;
																//criar o no e a aresta
	if((nodeAux = createNode(vert2)) == NULL) return NO_MEM;
	if((nodeAux->Elem = createEdge(pcost)) == NULL){
		free(nodeAux);
		return NO_MEM;}
																//determinar posiçao de inserçao e inserir aresta
	if(pvert1->adj == NULL || pvert1->adj->index > vert2){
		nodeAux->next = pvert1->adj;							//inserir na cabeça da lista de arestas
		pvert1->adj = nodeAux;}
	else{														//inserir a frente do no de inserçao
		if((nodeIns = inPosition(pvert1->adj, vert2)) == NULL){
			destroyNode(&nodeAux);								//aresta ja existe
			return EDGE_REP;}
		nodeAux->next = nodeIns->next;
		if(nodeAux->next != NULL) nodeAux->next->prev = nodeAux;
		nodeAux->prev = nodeIns;
		nodeIns->next = nodeAux;
	}
	nodeAux->adj = pvert2;										//ligar vertice 1 ao vertice 2
	vertice = (Vert) pvert1->Elem;
	vertice->outDegr++;											//actualizar grau emergente do vertice
	vertice = (Vert) pvert2->Elem;
	vertice->inDegr++;											//actualizar grau incidente do vertice
	ptr->numEdge++;												//actualizar numero de arestas
	return OK;
}


int insertReverseEdge(Graph ptr, unsigned int vert2, unsigned int vert1, int pcost){
	insertEdge(ptr, vert2, vert1, pcost);
	return OK;}


int removeEdge(Graph ptr, unsigned int vert1, unsigned int vert2){
	Vert vertice;
	Node rem;													//posiçao de remoçao da aresta
	Node pvert1, pvert2;										//posiçao dos vertices adjacentes

	if(ptr == NULL) return NO_GRAPH;
	if(ptr->numVert == 0) return NO_VERT;
	if(ptr->numEdge == 0 || vert1 == vert2) return NO_EDGE;
																//verificar se existem os vertices
	if((pvert1 = outPosition(ptr->head, vert1)) == NULL) return NO_VERT;
	if((pvert2 = outPosition(ptr->head, vert2)) == NULL) return NO_VERT;
																//determinar posiçao de remoçao da aresta
	if((rem = outPosition(pvert1->adj, vert2)) == NULL) return NO_EDGE;
																//remoçao da aresta
	if(rem == pvert1->adj){										//remoçao da aresta na cabeça da lista de arestas
		if(rem->next != NULL) rem->next->prev = NULL;
		pvert1->adj = rem->next; }
	else{														//remoçao de outra aresta do vertice
		rem->prev->next = rem->next;
		if(rem->next != NULL) rem->next->prev = rem->prev;
	}
	destroyNode(&rem);											//destruir nó com aresta
	vertice = (Vert) pvert1->Elem;
	vertice->outDegr--;											//actualizar grau emergente do vertice 1
	vertice = (Vert) pvert2->Elem;
	vertice->inDegr--;											//actualizar grau incidente do vertice 2
	ptr->numEdge--;												//actualizar numero de arestas
	return OK;
}


int removeReverseEdge(Graph ptr, unsigned int vert2, unsigned int vert1){
	removeEdge(ptr, vert2, vert1);
	return OK;
}


int numberVert(Graph ptr, unsigned int *nvert){
	if(ptr == NULL) return NO_GRAPH;
	if(nvert == NULL) return NULL_PTR;
	*nvert = ptr->numVert;
	return OK;
}


int numberEdge(Graph ptr, unsigned int *nedge){
	if(ptr == NULL) return NO_GRAPH;
	if(nedge == NULL) return NULL_PTR;
	*nedge = ptr->numEdge;
	return OK;
}


int getVertList(Graph ptr, unsigned int vert, char *vertlist){
	Node pvert, pedge;
	Edge edg;
	char nodelist[20];

	if(ptr == NULL) return NO_GRAPH;
	if(vert > ptr->numVert) return NO_VERT;
	if(vertlist == NULL) return NULL_PTR;

	vert--;
	for(pvert = ptr->head; vert > 0; vert--)
		pvert = pvert->next;

	sprintf(nodelist, "Vertice %d > ", pvert->index);
	strcpy(vertlist, nodelist);

	for(pedge = pvert->adj; pedge != NULL; pedge = pedge->next){
		sprintf(nodelist, "%d (", pedge->index);
		strcat(vertlist, nodelist);
		edg = (Edge)pedge->Elem;
		sprintf(nodelist, "%d) ", edg->cost);
		strcat(vertlist, nodelist);
	}
	return OK;
}


/*Travessia em largura do grafo*/

void breadthSearchQueue(Node pvert, unsigned int seq[], unsigned int *nv){
	Queue q;
	Node vertice = pvert;
	Node edg;

	q = queueCreate(sizeof(Node));									//criar fila
	vertice->Visit = 1;												//marcar vertice
	queueEnqueue(q, vertice);										//por vertice na fila
	while(queueEmpty(q) == 0){
		queueDequeue(q, &vertice);									//tirar vertice da fila
		seq[(*nv)++] = vertice->index;								//por vertice na sequencia
		for(edg = vertice->adj; edg != NULL; edg = edg->next)
			if(!edg->adj->Visit){									//ver se o vertice adjacente foi visitado
				edg->adj->Visit = 1;								//marcar vertice
				queueEnqueue(q, edg->adj); }						//por vertice na fila
	}
	queueDestroy(&q);												//destruir fila
}


int graphBreadth(Graph ptr, unsigned int seq[]){
	Node vertice;
	unsigned int I = 0;

	if(ptr == NULL) return NO_GRAPH;
	if(ptr->numVert == 0) return GRAPH_EMPTY;

	for(vertice = ptr->head; vertice != NULL; vertice = vertice->next)
		vertice->Visit = 0;
	for(vertice = ptr->head; vertice != NULL; vertice = vertice->next)
		if(!vertice->Visit) breadthSearchQueue(vertice, seq, &I);
	return OK;
}



/**
 * @fn createVert
 * @brief Funçao que cria o vertice do grafo. Retorna apontador para o vertice criado ou NULL, caso nao consiga criar
 */
static Vert createVert(){
	Vert vertice;

	if((vertice = (void*)malloc(sizeof(struct vertex))) == NULL)
		return NULL;
	vertice->inDegr = 0;												//inicializa grau incidente
	vertice->outDegr = 0;												//inicializa grau emergente
	return vertice;
}

/**
 * @fn createEdge
 * @brief Funçao que cria a aresta do grafo. Retorna apontador da aresta criada ou NULL, caso nao consigo criar
 */
static Edge createEdge(int pcost){
	Edge edg;

	if((edg = (void*)malloc(sizeof(struct edge))) == NULL)
		return NULL;
	edg->cost = pcost;													//armazena o custo da aresta
	return edg;
}

/**
 * @fn createNode
 * @brief Funçao que cria o no da lista de vertices ou de arestas. Retorna apontador para o no criado ou NULL, caso nao consiga criar
 */
static Node createNode(unsigned int num){
	Node aux;

	if((aux = (Node)malloc(sizeof(struct node))) == NULL)
		return NULL;
	aux->next = NULL;													//no seguinte a NULL
	aux->prev = NULL;													//no anterior a NULL
	aux->adj = NULL;													//lista de adjacencias nula
	aux->index = num;													//guarda identificador do no
	return aux;
}

/**
 * @fn destroyNode
 * @brief Funçao que liberta a memoria ocupada pelo no, lista de arestas ou de vertices, e pelo elemento ligado
 */
static void destroyNode(Node *ptr){
	if(*ptr == NULL) return;
	free((*ptr)->Elem);
	free(*ptr);
	*ptr = NULL;
}

/**
 * @fn inPosition
 * @brief Funçao de pesquisa para inserçao, que devolve o apontador para o nó à frente do qual deve ser feita a inserçao do novo vertice, ou NULL caso ja exista
 */
static Node inPosition(Node no, unsigned int num){
	Node aux, ant;
	for(aux = no; aux != NULL; aux = aux->next){
		if(aux->index >= num) break;
		ant = aux; }
	if(aux == NULL || aux->index > num) return ant;
	else return NULL;													//ja existe
}

/**
 * @fn outPosition
 * @brief Funçao de pesquisa para a remoçao, que devolve o apontador para o nó onde se encontra o vertice, ou NULL caso o vertice nao exista
 */
static Node outPosition(Node no, unsigned int num){
	Node aux;
	for(aux = no; aux != NULL; aux = aux->next)
		if(aux->index == num) break;
	return aux;
}


/**
 * @fn outNumVert
 * @brief Função que devolve o valor de numVert para usar na queue
 */
int outNumVert(Graph ptr){
	if(ptr == NULL) return (unsigned int)NO_GRAPH;
	int nvertices = ptr->numVert;
	return nvertices;
}